import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1519. 子树中标签相同的节点数
 * https://leetcode-cn.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/
 */
public class Solutions_1519 {
    public static void main(String[] args) {
        int n = 7;
        int[][] edges = {{0, 1}, {0, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 6}};
        String labels = "abaedcd";  // output: {2, 1, 1, 1, 1, 1, 1}
//        解释：节点 0 的标签为 'a' ，以 'a' 为根节点的子树中，节点 2 的标签也是 'a' ，因此答案为 2 。注意树中的每个节点都是这棵子树的一部分。
//        节点 1 的标签为 'b' ，节点 1 的子树包含节点 1、4 和 5，但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。

//        int n = 4;
//        int[][] edges = {{0, 1}, {1, 2}, {0, 3}};
//        String labels = "bbbb";  // output: {4, 2, 1, 1}
//        解释：节点 2 的子树中只有节点 2 ，所以答案为 1 。
//        节点 3 的子树中只有节点 3 ，所以答案为 1 。
//        节点 1 的子树中包含节点 1 和 2 ，标签都是 'b' ，因此答案为 2 。
//        节点 0 的子树中包含节点 0、1、2 和 3，标签都是 'b'，因此答案为 4 。

//        int n = 5;
//        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {0, 4}};
//        String labels = "aabab";  // output: {3, 2, 1, 1, 1}

//        int n = 6;
//        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {3, 4}, {4, 5}};
//        String labels = "cbabaa";  // output: {1, 2, 1, 1, 2, 1}

//        int n = 7;
//        int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}};
//        String labels = "aaabaaa";  // output: {6, 5, 4, 1, 3, 2, 1}

        int[] result = countSubTrees(n, edges, labels);
        System.out.println(Arrays.toString(result));
    }

    public static int[] countSubTrees(int n, int[][] edges, String labels) {
        if (n == 1) {
            return new int[]{1};
        }
        // list.get(0) = {1, 2}，表示节点 0 与 节点 1、节点 2 之间存在一条边
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        // 预处理：遍历 edges，将各个节点之间的关联关系，保存到 list 中
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            list.get(a).add(b);
            list.get(b).add(a);
        }
        // 已访问过的节点，将不再访问
        boolean[] visited = new boolean[n];
        // 根节点为 0
        int[] res = new int[n];
        dfs(list, labels, 0, visited, res);
        return res;
    }

    public static int[] dfs(List<List<Integer>> list, String labels, int cur, boolean[] visited, int[] res) {
        // 标记为已访问，防止通过子节点再遍历到当前节点，造成死循环
        visited[cur] = true;
        // counts[1] = 2，表示 cur 节点下，有 2 个标签为 b 的节点（可能也包括自己）
        int[] counts = new int[26];
        // cur 的子节点
        List<Integer> children = list.get(cur);
        for (int child : children) {
            if (!visited[child]) {
                // 未访问过子节点，递归查找
                int[] ans = dfs(list, labels, child, visited, res);
                // 对子节点遍历后返回的标签记录，添加到 counts 中，因为子节点的子节点，也是当前节点的子节点
                for (int i = 0; i < 26; i++) {
                    counts[i] += ans[i];
                }
            }
        }
        char c = labels.charAt(cur);
        // 节点 cur 下，标签为 c 的节点共有 counts[c - 'a'] 个
        counts[c - 'a'] ++;
        // 节点 cur 下的子节点递归结束，那么记录下 cur 的结果
        res[cur] += counts[c - 'a'];
        return counts;
    }
}
